package com.mccken.practice.top100.Top_1$20.top_12;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Stack;

/**
 * @program: mccken-collect
 * @description:
 * @author: mccken
 * @create: 2024-01-02 15:49
 **/
public class Merge {

	public int[][] merge(int[][] intervals) {
		int len = intervals.length;
		if (len == 1) {
			return intervals;
		}

		// 排序
		Arrays.sort(intervals, Comparator.comparingInt(interval -> interval[0]));

		Stack<int[]> merge = new Stack<>();
		merge.push(intervals[0]);
		for (int i = 1; i < intervals.length; i++) {
			int[] pre = merge.peek();
			int pre_end = pre[1];
			int cur_start = intervals[i][0];
			if (cur_start <= pre_end) {
				if (pre[1] < intervals[i][1]) {
					pre[1] = intervals[i][1];
				}
			} else {
				merge.push(intervals[i]);
			}
		}

		int[][] res = new int[merge.size()][2];
		int i = 0;
		for (int[] ints : merge) {
			res[i++] = ints;
		}

		return res;
	}

	public static void main(String[] args) {
		Merge merge = new Merge();
		int[][] ints1 = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
		int[][] ints2 = {{1, 4}, {2, 3}};
		// [[2,3],[2,2],[3,3],[1,3],[5,7],[2,2],[4,6]]
		int[][] ints3 = {{2, 3}, {2, 2},{3,3},{1,3},{5,7},{2,2},{4,6}};
//		System.out.println(Arrays.deepToString(merge.merge(ints1)));
//		System.out.println(Arrays.deepToString(merge.merge(ints2)));
		System.out.println(Arrays.deepToString(merge.merge(ints3)));

	}
}
